package ru.usu.gv.gui.clustering;

import ru.usu.gv.utils.RandomUtilities;
import it.unimi.dsi.fastutil.ints.Int2IntMap;
import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntList;
import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
import it.unimi.dsi.fastutil.ints.IntSet;

import java.util.Arrays;

/**
 * @author spupyrev
 * 17.11.2008
 * 
 * TODO:
 * 	kill renumber (renumber after one_level?)
 */
public class Community
{
	public static int MAX_COMMUNITY_SIZE = 250;

	private BinaryGraph g;
	private int size;
	private int[] n2c;
	private int[] in;
	private int[] tot;
	private int[] totCount;
	private int nb_pass;
	private double minModularity;

	public Community(BinaryGraph graph, int nbp, double minModularity)
	{
		this.g = graph;
		this.nb_pass = nbp;
		this.minModularity = minModularity;

		size = graph.n;

		n2c = new int[size];
		in = new int[size];
		tot = new int[size];
		totCount = new int[size];

		for (int i = 0; i < size; i++)
		{
			n2c[i] = i;
			in[i] = graph.countSelfloops(i);
			tot[i] = graph.getWeightedDegree(i);
			totCount[i] = 1;
		}

	}

	private void insert(int node, int comm, int dnodecomm)
	{
		tot[comm] += g.getWeightedDegree(node);
		totCount[comm] += 1;
		in[comm] += 2 * dnodecomm + g.countSelfloops(node);
		n2c[node] = comm;
	}

	private void remove(int node, int comm, int dnodecomm)
	{
		assert (node >= 0 && node < size);

		tot[comm] -= g.getWeightedDegree(node);
		totCount[comm] -= 1;
		in[comm] -= 2 * dnodecomm + g.countSelfloops(node);
		n2c[node] = -1;
	}

	private double gainModularity(int node, int comm, int dnodecomm)
	{
		assert (node >= 0 && node < size);

		double totc = tot[comm];
		double degc = g.getWeightedDegree(node);
		double m2 = g.totalWeight;
		double dnc = dnodecomm;

		return (dnc - totc * degc / m2);
	}

	public double modularity()
	{
		double q = 0.;
		double m2 = g.totalWeight;

		for (int i = 0; i < size; i++)
		{
			if (tot[i] > 0)
				q += in[i] / m2 - (tot[i] / m2) * (tot[i] / m2);
		}

		return q;
	}

	public void display_partition()
	{
		//TODO: kill renumber!!!
		int[] renumber = new int[size];
		Arrays.fill(renumber, -1);
		for (int node = 0; node < size; node++)
		{
			renumber[n2c[node]]++;
		}

		int final2 = 0;
		for (int i = 0; i < size; i++)
			if (renumber[i] != -1)
				renumber[i] = final2++;

		for (int i = 0; i < size; i++)
			System.out.println("" + i + " " + renumber[n2c[i]]);
	}

	// computation of all neighboring communities of current node
	private Int2IntMap neigh_comm(int node)
	{
		Int2IntMap res = new Int2IntOpenHashMap();

		res.put(n2c[node], 0);
		for (int i = 0; i < g.links[node].length; i++)
		{
			int neigh = g.links[node][i];
			int neigh_comm = n2c[neigh];
			int neigh_weight = g.weights[node][i];

			if (neigh != node)
			{
				updateIntMap(res, neigh_comm, neigh_weight);
			}
		}

		return res;
	}

	public double one_level()
	{
		boolean improvement = false;
		int nb_pass_done = 0;
		double new_mod = modularity();
		double cur_mod = new_mod;

		// repeat while 
		//   there is an improvement of modularity
		//   or there is an improvement of modularity greater than a given epsilon 
		//   or a predefined number of pass have been done

		//TODO: rewrite
		int[] random_order = new int[size];
		for (int i = 0; i < size; i++)
			random_order[i] = i;
		for (int i = 0; i < size - 1; i++)
		{
			int rand_pos = RandomUtilities.nextInt(size - i) + i;
			int tmp = random_order[i];
			random_order[i] = random_order[rand_pos];
			random_order[rand_pos] = tmp;
		}

		IntSet freeComm = new IntOpenHashSet();
		Int2IntMap comm2Free = new Int2IntOpenHashMap();

		do
		{
			cur_mod = new_mod;
			improvement = false;
			nb_pass_done++;

			// for each node: remove the node from its community and insert it in the best community
			for (int node_tmp = 0; node_tmp < size; node_tmp++)
			{
				int node = node_tmp;
				int node_comm = n2c[node];

				// computation of all neighboring communities of current node
				Int2IntMap ncomm = neigh_comm(node);

				// remove node from its current community
				remove(node, node_comm, ncomm.get(node_comm));
				if (totCount[node_comm] == 0)
					freeComm.add(node_comm);

				// compute the nearest community for node
				// default choice for future insertion is the former community
				int best_comm = node_comm;
				int best_nblinks = 0;
				double best_increase = 0.0;

				for (int it : ncomm.keySet())
				{
					double increase = gainModularity(node, it, ncomm.get(it));
					if (increase > best_increase /*&& totCount[it] < MAX_COMMUNITY_SIZE*/)
					{
						best_comm = it;
						best_nblinks = ncomm.get(it);
						best_increase = increase;
					}
				}

				// insert node in the nearest community
				while (totCount[best_comm] >= MAX_COMMUNITY_SIZE)
				{
					//find free and move it there instead
					if (!comm2Free.containsKey(best_comm))
					{
						comm2Free.put(best_comm, freeComm.iterator().nextInt());
						//if no such elemenent then it is internal error
					}
					best_comm = comm2Free.get(best_comm);
					best_nblinks = (ncomm.containsKey(best_comm) ? ncomm.get(best_comm) : 0);

					//if it is filled too
					if (totCount[best_comm] >= MAX_COMMUNITY_SIZE)
						comm2Free.remove(best_comm);
				}

				insert(node, best_comm, best_nblinks);
				if (totCount[best_comm] > 0)
					freeComm.remove(best_comm);

				if (best_comm != node_comm)
					improvement = true;
			}

			new_mod = modularity();
			System.out.println("pass number " + nb_pass_done + " of " + nb_pass + " : " + new_mod + " " + cur_mod);

			//break;
		}
		while (improvement && new_mod - cur_mod > minModularity && nb_pass_done != nb_pass);

		return new_mod;
	}

	public BinaryGraph partition2graph_binary()
	{
		Int2ObjectMap<IntList> comm = new Int2ObjectOpenHashMap<IntList>();
		Int2IntMap comm2Order = new Int2IntOpenHashMap();
		IntList order = new IntArrayList();
		for (int i = 0; i < size; i++)
		{
			if (!comm.containsKey(n2c[i]))
			{
				comm.put(n2c[i], new IntArrayList());
				order.add(n2c[i]);
				comm2Order.put(n2c[i], order.size() - 1);
			}

			comm.get(n2c[i]).add(i);
		}

		// unweigthed to weighted
		BinaryGraph g2 = new BinaryGraph();
		g2.n = order.size();
		g2.links = new int[order.size()][];
		g2.weights = new int[order.size()][];

		for (int ci = 0; ci < order.size(); ci++)
		{
			int cIndex = order.getInt(ci);
			Int2IntMap m = new Int2IntOpenHashMap();

			for (int vIndex : comm.get(cIndex))
			{
				for (int i = 0; i < g.links[vIndex].length; i++)
				{
					int neigh = g.links[vIndex][i];
					int neigh_comm = comm2Order.get(n2c[neigh]);
					int neigh_weight = g.weights[vIndex][i];

					updateIntMap(m, neigh_comm, neigh_weight);
				}
			}

			g2.links[ci] = new int[m.size()];
			g2.weights[ci] = new int[m.size()];

			int where = 0;
			for (int it : m.keySet())
			{
				g2.totalWeight += m.get(it);
				g2.links[ci][where] = it;
				g2.weights[ci][where] = m.get(it);
				where++;
			}
		}

		return g2;
	}

	public Cluster prepareCluster(Cluster rootCluster, BinaryGraph binaryGraph)
	{
		Cluster cluster = new Cluster(binaryGraph);
		Int2ObjectMap<IntList> comm = new Int2ObjectOpenHashMap<IntList>();
		IntList order = new IntArrayList();
		for (int i = 0; i < size; i++)
		{
			if (!comm.containsKey(n2c[i]))
			{
				comm.put(n2c[i], new IntArrayList());
				order.add(n2c[i]);
			}

			comm.get(n2c[i]).add(i);
		}

		for (int cIndex : order)
		{
			BinaryGraph subBinaryGraph = rootCluster.constructSubBinaryGraph(comm.get(cIndex));
			Cluster subCluster = new Cluster(subBinaryGraph);
			for (int vIndex : comm.get(cIndex))
			{
				if (rootCluster.containsVertexes())
					subCluster.addVertex(rootCluster.getVertexes().get(vIndex));
				else
					subCluster.addSubCluster(rootCluster.getSubClusters().get(vIndex));
			}

			cluster.addSubCluster(subCluster);
		}

		return cluster;
	}

	private void updateIntMap(Int2IntMap m, int key, int value)
	{
		m.put(key, m.get(key) + value);
	}
}
